package ljl.codetop300;

import commons.WrongAnswer;

import java.util.HashMap;
import java.util.Map;

public class _91_num_decodings {

  @WrongAnswer("timeout")
  static class test {
    int res;
    public int numDecodings(String s) {
      backtrack(s.toCharArray(), 0);
      return res;
    }

    void backtrack(char[] chars, int i) {
      if (i == chars.length) {
        res++;
        return;
      }
      if (chars[i] != '0') {
        backtrack(chars, i + 1);
        if (i + 1 < chars.length) {
          int num = chars[i] - '0';
          num = num * 10 + chars[i + 1] - '0';
          if (num < 27) {
            backtrack(chars, i + 2);
          }
        }
      }
    }
  }

  static class off_dp1 {
    public int numDecodings(String s) {
      int n = s.length();
      int[] f = new int[n + 1];
      f[0] = 1;
      for (int i = 1; i <= n; ++i) {
        if (s.charAt(i - 1) != '0') {
          f[i] = f[i - 1];
        }
        if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
          f[i] += f[i - 2];
        }
      }
      return f[n];
    }
  }

  static class copy_off_dp1 {
    public int numDecodings(String s) {
      int len = s.length();
      int[] dp = new int[len + 1];
      dp[0] = 1;
      for (int i = 1; i <= len; i++) {
        if (s.charAt(i - 1) == '0') dp[i] = dp[i - 1];
        if (i > 1 && s.charAt(i - 2) != '0') {
          int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
          if (num < 27) dp[i] += dp[i - 2];
        }
      }
      return dp[len];
    }
  }

  static class off_dp2 {
    public int numDecodings(String s) {
      int n = s.length();
      // a = f[i-2], b = f[i-1], c=f[i]
      int a = 0, b = 1, c = 0;
      for (int i = 1; i <= n; ++i) {
        c = 0;
        if (s.charAt(i - 1) != '0') {
          c = b;
        }
        if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
          c += a;
        }
        a = b;
        b = c;
      }
      return c;
    }
  }

  static class copy_off_dp2 {
    // 1 2
    public int numDecodings(String s) {
      int n = s.length();
      int a = 0, b = 1, c;
      for (int i = 0; i < n; i++) {
        c = 0;
        if (s.charAt(i) != '0') c = b;
        if (i > 0 && s.charAt(i - 1) != '0') {
          int num = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';
          if (num < 27) c += a;
        }
        a = b;
        b = c;
      }
      return b;
    }
  }
}
